//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
// 
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
//
// Related Topics 链表 双指针 分治 排序 归并排序 👍 2078 👎 0


package LeetCode.editor.cn;

import java.util.List;

/**
 * @author ldltd
 * @date 2023-08-16 12:26:38
 * @description 148.排序链表
 */
public class SortList{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new SortList().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode sortList1(ListNode head) {
		return sortList1(head,null);
    }
	/*自顶向下，分治归并排序
	* 时间O nlogn  空间Logn*/
	public ListNode sortList1(ListNode head,ListNode tail){
		//两种边界
		if(head==null)  return head;
		if(head.next==tail){
			head.next=null;
			return head;
		}
		ListNode slow=head,fast=head;
		while (fast!=tail){
			slow=slow.next;
			fast=fast.next;
			if(fast!=tail){
				fast=fast.next;
			}
		}
		ListNode mid=slow;
		ListNode list1=sortList1(head,mid);
		ListNode list2=sortList1(mid,tail);
		ListNode sorted=merge(list1,list2);
		return sorted;
	}

	/*自底向上
	 * 时间O nlogn  空间O1
	 * 每次把链表变成len长的子链表，然后合并，依次加倍直到全部排序完*/
	public ListNode sortList2(ListNode head){
		if(head==null) return head;
		int len=0;
		ListNode p=head;
		//计算长度
		while (p!=null){
			p=p.next;
			len++;
		}
		//哑结点
		ListNode res = new ListNode(-1, head);
		//长度从1 开始，每次加倍
		for (int i = 1	; i < len; i<<=1) {
			ListNode pre=res,curr=res.next;
			//分割区间
			while(curr!=null){
				ListNode head1=curr;
				//找到第一个区间最后一个元素
				for (int j = 1; j < i&&curr.next!=null; j++) {
					curr=curr.next;
				}
				//保存这个区间下一个元素
				ListNode head2=curr.next;
				//将第一个区间的末尾置空，方便做终点
				curr.next=null;
				//计算第二个区间
				curr=head2;
				for (int j = 1; j < i&&curr!=null&&curr.next!=null; j++) {
					curr=curr.next;
				}
				ListNode next=null;
				//如果没有遍历完，则保存第二个区间末尾的下一个元素，并将末尾置空，方便作为终点
				if(curr!=null){
					next=curr.next;
					curr.next=null;
				}
				//将前两个区间先合并
				ListNode merged=merge(head1,head2);
				pre.next=merged;
				//将pre放到两个区间的末尾的前一个不为空的位置
				while (pre.next!=null){
					pre=pre.next;
				}
				//继续拆分
				curr=next;
			}
		}
		return res.next;
	}
	public ListNode merge(ListNode head1,ListNode head2){
		ListNode res = new ListNode(0);
		ListNode t=res,t1=head1,t2=head2;
		while(t1!=null&&t2!=null){
			if(t1.val<=t2.val){
				t.next=t1;
				t1=t1.next;
			}else {
				t.next=t2;
				t2=t2.next;
			}
			t=t.next;
		}
		//扫尾
		if(t1!=null){
			t.next=t1;
		}else if(t2!=null){
			t.next=t2;
		}
		return res.next;
	}

	public ListNode sortList(ListNode head){
		if(head==null) return head;
		int len=0;
		ListNode p=head;
		while (p!=null){
			p=p.next;
			len++;
		}
		ListNode res=new ListNode(0,head);
		//长度从1开始，依次加倍
		for (int i = 1; i < len; i<<=1) {
			ListNode pre=res,curr=pre.next;
			while (curr!=null){
				ListNode head1 =curr;
				for (int j = 0; j < i && curr.next != null; j++) {
					curr=curr.next;
				}
				//下一个元素
				ListNode head2=curr.next;
				//将第一个区间末尾置空，做终点
				curr.next=null;
				//找第二个区间
				curr=head2;
				for (int j = 1; j <i&&curr!=null&&curr.next!=null ; j++) {
					curr=curr.next;
				}
				ListNode next=null;
				if(curr!=null){
					next=curr.next;
					curr.next=null;
				}
				//将前两个区间合并
				ListNode merged=merge(head1,head2);
				pre.next=merged;
				while (pre.next!=null){
					pre=pre.next;
				}
				curr=next;
			}
		}
		return res.next;
	}

	public ListNode merge1(ListNode t1,ListNode t2){
		ListNode p1=t1;
		ListNode p2=t2;
		ListNode res=new ListNode(0);
		ListNode p=res;
		while (t1!=null&&t2!=null){
			if(t1.val> t2.val){
				p.next=t1;
				t1=t1.next;
			}else {
				p.next=t2;
			}
			p=p.next;
		}
		if(t1!=null){
			t1.next=t1;
		}else if(t2!=null){
			t2.next=t2;
		}
		return res.next;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
